package com.test.daily.leetcode.y2022.m06.day0607.v03;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/7 下午 11:03
 * @version: 1.0
 */
public class Solution {
    public static int win1(int[] arr) {
        int first = f1(arr, 0, arr.length - 1);
        int second = g1(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }

    public static int f1(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int left = arr[L] + g1(arr, L + 1, R);
        int right = arr[R] + g1(arr, L, R - 1);
        return Math.max(left, right);
    }

    public static int g1(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int left = arr[L] + f1(arr, L + 1, R);
        int right = arr[R] + f1(arr, L, R - 1);
        return Math.min(left, right);
    }

    public static int win2(int[] arr) {
        int[][] fmap = new int[arr.length][arr.length];
        int[][] gmap = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = f2(arr, 0, arr.length - 1, fmap);
        int second = g2(arr, 0, arr.length - 1, gmap);
        return Math.max(first, second);

    }

    public static int f2(int[] arr, int L, int R, int[][] fmap) {
        if (fmap[L][R] != -1) {
            return fmap[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        } else {
            int left = arr[L] + g2(arr, L + 1, R, fmap);
            int right = arr[R] + g2(arr, L, R - 1, fmap);
            ans = Math.max(left, right);
        }
        fmap[L][R] = ans;
        return ans;
    }

    public static int g2(int[] arr, int L, int R, int[][] gmap) {
        if (gmap[L][R] != -1) {
            return gmap[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        }
        int left = arr[L] + f2(arr, L + 1, R, gmap);
        int right = arr[R] + f2(arr, L, R - 1, gmap);
        ans = Math.min(left, right);
        gmap[L][R] = ans;
        return ans;
    }

    public static int winner3(int[] arr) {
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < arr.length; i++) {
            fmap[i][i] = arr[i];
            gmap[i][i] = arr[i];
        }

        // int R = 0;
        for (int start = 1; start < arr.length; start++) {
            int L = 0;
            int R = start;
            while (R < N) {
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(arr[L] + fmap[L + 1][R], arr[R] + fmap[L][R - 1]);
                L++;
                R++;
            }
        }

        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }
}
